home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_6.2 / XVORA / VORA.C < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  15.5 KB  |  731 lines
  1. /*
  2.  * V(oronoi)A(nalysis)
  3.  *
  4.  * routines to analyze Voronoi diagram, given in file of type .vdt,
  5.  * generated by xvor.c
  6.  *
  7.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <math.h>
  11. #include "vora.h"
  12.  
  13.  
  14. /* global */
  15. int EDGE_SORT = 0;
  16. struct Tuple em;
  17. extern int ACTIVE_AOI;
  18.  
  19.  
  20. #define    EPS    0.1                 /* lower limit for poly edge length */
  21.      /* an edge of len < 1 pix will not */
  22.      /* appear on the display */
  23.  
  24. /* 
  25.  * hsbaird macros (for later use)
  26.  */
  27. #define AREA(a,b,c) ( ((-((c)->y-(b)->y))*((a)->x-(b)->x)+((c)->x-(b)->x)*((a)->y-(b)->y)) )
  28.  
  29. /* 
  30.  * macroes for use within winding order function 
  31.  */
  32. /* dot product */
  33. #define DOT(a,b) ( (a).x*(b).x+(a).y*(b).y )
  34.  
  35. /* perp product */
  36. #define PERP(a,b) ( -((a).y)*(b).x+(a).x*(b).y )
  37.  
  38. /* 
  39.  * return the quadrant no: 0,1,2,3 of pt `a' wrt to the X-Y coordinate system
  40.  * defined by aligning the positive X-axis along vector `o' (`a' is a vector
  41.  * wrt to `o') 
  42.  */
  43. #define QUAD(a,o) ( ((DOT((o),(a)))>=0) ?   ( (PERP((o),(a))>=0) ? 0 : 3) : ( (PERP((o),(a))>=0) ? 1 : 2) )
  44.  
  45.  
  46. /* 
  47.  * return -1,0,1 as pt `a' is less than, equal to, or greater than pt `b' in
  48.  * counterclockwise winding order about an (implicit) center `HULL_c', where
  49.  * the vector `o' defines the `origin' direction 
  50.  */
  51. int qa, qb;
  52. struct Pix o;
  53. #define WIND(a,b,o) ( ((qa=QUAD((a),(o))) == (qb=QUAD((b),(o)))) ?   SIGN(PERP((a),(b))) : SIGN(qb-qa) )
  54.  
  55.  
  56.  
  57. #undef    SHOW_SORT
  58.  
  59.  
  60. /*
  61.  * evaluate edge midpoint coordinates
  62.  */
  63. struct Tuple *
  64. edge_mp (v1, v2, index)
  65.      struct vSite *v1, *v2;
  66.      int index;
  67. {
  68.   struct Tuple *emp = &em;
  69.  
  70.   emp->x = (float) 0.5 *(v1->coord.x + v2->coord.x);
  71.   emp->y = (float) 0.5 *(v1->coord.y + v2->coord.y);
  72.   emp->index = index;
  73.  
  74.   return (emp);
  75. }
  76.  
  77.  
  78. /*
  79.  * winding number function, for use in edge sort
  80.  */
  81. int
  82. winding_ccwT (r1, r2)
  83.      struct Tuple *r1, *r2;
  84. {
  85.   struct Pix a, b;
  86.  
  87.   a.x = r1->x;
  88.   a.y = r1->y;
  89.   b.x = r2->x;
  90.   b.y = r2->y;
  91.  
  92.   return (WIND (a, b, o));
  93. }
  94.  
  95. /*
  96.  * sort polygon edges;
  97.  * the implementation is adapted from h. s. baird (->p_app.c): it relies
  98.  * on a sort with respect to ``winding number'' and employs the macros
  99.  * defined above; a site interior to the polygon is needed: this is 
  100.  * the orig. site *s;
  101.  */
  102. void
  103. sort_poly_edges (pem, s, p)
  104.      struct Tuple *pem;
  105.      struct vSite *s;
  106.      struct vPoly *p;
  107. {
  108.  
  109.   /*define ``origin'' vector, from interior point *s to 1st pt */
  110.   o.x = pem->x - s->coord.x;
  111.   o.y = pem->y - s->coord.y;
  112.  
  113. #if defined(LINUX)
  114.   qsort (pem, p->ne, sizeof (struct Tuple *), (__compar_fn_t) winding_ccwT);
  115. #else
  116.   qsort (pem, p->ne, sizeof (struct Tuple *), winding_ccwT);
  117. #endif
  118.  
  119.  
  120. /*
  121.  * use the reordered sequence of polygon edges...
  122.  */
  123.  
  124. }
  125.  
  126.  
  127.  
  128. /*
  129.  * comparison function for qsort():
  130.  * sort array of edges in order of increasing site indices, sO, sF
  131.  */
  132. int
  133. esO_comp (e1, e2)
  134.      struct vEdge *e1, *e2;
  135. {
  136.  
  137.   if (e1->sO < e2->sO)
  138.     return (-1);
  139.   if (e1->sO > e2->sO)
  140.     return (1);
  141.  
  142.   return (0);
  143. }
  144.  
  145. /*
  146.  * comparison function for qsort():
  147.  * sort array of edges in order of increasing site indices, sO, sF
  148.  */
  149. int
  150. esF_comp (e1, e2)
  151.      struct vEdge *e1, *e2;
  152. {
  153.  
  154.   if (e1->sF < e2->sF)
  155.     return (-1);
  156.   if (e1->sF > e2->sF)
  157.     return (1);
  158.  
  159.   return (0);
  160. }
  161.  
  162.  
  163. /*
  164.  * determine length of a given line segment,
  165.  * i. e. Voronoi edge or bisector
  166.  */
  167. double
  168. slen (v1, v2)
  169.      struct vSite *v1, *v2;
  170. {
  171.   double len;
  172.   double dx, dy;
  173.  
  174.   dx = (double) (v1->coord.x - v2->coord.x);
  175.   dy = (double) (v1->coord.y - v2->coord.y);
  176.   len = sqrt (dx * dx + dy * dy);
  177.   if ((-EPS < len) && (len < EPS))
  178.     len = 0.0;
  179.  
  180.   return (len);
  181. }
  182.  
  183.  
  184.  
  185.  
  186. /*
  187.  * analyze site properties; return max coodination number in set
  188.  *
  189.  * note: 
  190.  * (s+is)->nnn is being redetermined here: this is not necessary 
  191.  * (see site_coordination()) and should be improved; ms, 4/94;
  192.  * 
  193.  * sites are presumed ta have been examined (in mark_eSites() and 
  194.  * in site_coordination()) for edge conditions
  195.  */
  196. int
  197. site_geom (struct vSite *s, struct vSite *v, struct vEdge *e, struct vPoly *p, int ns, int ne)
  198. {
  199.   int ie, is;
  200.   int e_vO, e_vF;
  201.   int efl, lfl;
  202.   double vE_len;
  203.  
  204.   int max_ne;
  205.  
  206. /* 
  207.  * search sF member, assumed sorted (see site_coordination())
  208.  */
  209.   ie = 0;
  210.   for (is = 0; is < ns; is++) { /* loop over sites */
  211.     (s + is)->nnn = 0;          /* count not nn sites */
  212.     (p + is)->ne = 0;           /* count nof Vpoly edges */
  213.     (p + is)->sitenbr = (s + is)->sitenbr;
  214.     (p + is)->aoiFlag = (s + is)->aoiFlag;
  215.     (p + is)->eFlag = (p + is)->lFlag = UnSet;
  216.  
  217. /*
  218.  * search sF member
  219.  */
  220.     efl = lfl = 0;
  221.     while ((e + ie)->sF == (s + is)->sitenbr) {
  222.       (s + is)->nnd[(s + is)->nnn] = (float) slen (s + ((e + ie)->sO), s + ((e + ie)->sF));
  223.       (s + is)->nnsi[(s + is)->nnn] = (e + ie)->sO;
  224.       (s + is)->nnn++;
  225.  
  226.       (p + is)->pei[(p + is)->ne] = (e + ie)->edgenbr;
  227.       e_vO = (e + ie)->vO;
  228.       e_vF = (e + ie)->vF;
  229.       if (check_e (e_vO, e_vF) == Set) {
  230.         (p + is)->vel[(p + is)->ne] = (float) -1.0;
  231.         efl++;
  232.       }
  233.       else {
  234.         if ((vE_len = slen (v + e_vO, v + e_vF)) == 0.0) {
  235.           (p + is)->vel[(p + is)->ne] = (float) -1.0;
  236.           lfl++;
  237.         }
  238.         else {                  /* edge too small to display */
  239.           (p + is)->vel[(p + is)->ne] = (float) vE_len;
  240.           if (vE_len <= 1.0)
  241.             lfl++;
  242.         }
  243.       }
  244.       (p + is)->ne++;
  245.       ie++;
  246.     }
  247.     if (efl > 0)
  248.       (p + is)->eFlag = Set;
  249.     if (lfl > 0)
  250.       (p + is)->lFlag = Set;
  251.   }
  252.  
  253.  
  254. /* 
  255.  * now, search sO member 
  256.  */
  257. #if defined(LINUX)
  258.   qsort (e, ne, sizeof (struct vEdge), (__compar_fn_t) esO_comp);
  259. #else
  260.   qsort (e, ne, sizeof (struct vEdge), esO_comp);
  261. #endif
  262. #ifdef SHOW_SORT
  263.   printf ("\n...edges after sorting in order of sO indices:\n");
  264.   for (ie = 0; ie < ne; ie++)
  265.     printf ("  e %3d:  vO: %3d vF: %3d  sO: %3d sF: %3d\n",
  266.             (e + ie)->edgenbr, (e + ie)->vO, (e + ie)->vF, (e + ie)->sO, (e + ie)->sF);
  267. #endif
  268.  
  269.   ie = 0;
  270.   for (is = 0; is < ns; is++) {
  271.     efl = lfl = 0;
  272.     while ((e + ie)->sO == (s + is)->sitenbr) {
  273.       (s + is)->nnd[(s + is)->nnn] = (float) slen (s + ((e + ie)->sO), s + ((e + ie)->sF));
  274.       (s + is)->nnsi[(s + is)->nnn] = (e + ie)->sF;
  275.       (s + is)->nnn++;
  276.  
  277.       (p + is)->pei[(p + is)->ne] = (e + ie)->edgenbr;
  278.       e_vO = (e + ie)->vO;
  279.       e_vF = (e + ie)->vF;
  280.       if (check_e (e_vO, e_vF) == Set) {
  281.         (p + is)->vel[(p + is)->ne] = (float) -1;
  282.         efl++;
  283.       }
  284.       else {
  285.         if ((vE_len = slen (v + e_vO, v + e_vF)) == 0.0) {
  286.           (p + is)->vel[(p + is)->ne] = (float) -1.0;
  287.           lfl++;
  288.         }
  289.         else {                  /* edge too small to display */
  290.           (p + is)->vel[(p + is)->ne] = (float) vE_len;
  291.           if (vE_len <= 1.0)
  292.             lfl++;
  293.         }
  294.       }
  295.       (p + is)->ne++;
  296.       ie++;
  297.     }
  298.     if (efl > 0)
  299.       (p + is)->eFlag = Set;
  300.     if (lfl > 0)
  301.       (p + is)->lFlag = Set;
  302.   }
  303.  
  304. /*
  305.  * determine max coordination number
  306.  */
  307.   max_ne = 0;
  308.   for (is = 0; is < ns; is++)
  309.     if ((p + is)->ne > max_ne)
  310.       max_ne = (p + is)->ne;
  311.  
  312.   return (max_ne);
  313. }
  314.  
  315.  
  316.  
  317.  
  318. /*
  319.  * comparison function for qsort():
  320.  * sort array of edges in order of increasing edge index
  321.  */
  322. int
  323. e_comp (e1, e2)
  324.      struct vEdge *e1, *e2;
  325. {
  326.  
  327.   if (e1->edgenbr < e2->edgenbr)
  328.     return (-1);
  329.   if (e1->edgenbr > e2->edgenbr)
  330.     return (1);
  331.  
  332.   return (0);
  333. }
  334.  
  335.  
  336. /*
  337.  * determine (signed) triangular area spanned by three supplied vertices
  338.  */
  339. double
  340. T_area (v1, v2, v3)
  341.      struct vSite *v1, *v2, *v3;
  342. {
  343.   double s_area;
  344.   double x1, x2, x3, y1, y2, y3;
  345.  
  346.   x1 = (double) (v1->coord.x);
  347.   x2 = (double) (v2->coord.x);
  348.   x3 = (double) (v3->coord.x);
  349.   y1 = (double) (v1->coord.y);
  350.   y2 = (double) (v2->coord.y);
  351.   y3 = (double) (v3->coord.y);
  352.  
  353.   s_area = (x1 * y2 - x2 * y1) + (x2 * y3 - x3 * y2) + (x3 * y1 - x1 * y3);
  354.   if ((-1.0e-10 < s_area) && (s_area < 1.0e-10))
  355.     s_area = 0.0;
  356.  
  357.   return (s_area);
  358. }
  359.  
  360.  
  361. /*
  362.  * check whether vertices defining edge are set to -1; 
  363.  * if so, set flag to Set status, otherwise, return UnSet;
  364.  */
  365. Boolean
  366. check_e (e_vO, e_vF)
  367.      int e_vO, e_vF;
  368. {
  369.  
  370.   if ((e_vO == -1) || (e_vF == -1))
  371.     return (Set);
  372.  
  373.   return (UnSet);
  374. }
  375.  
  376.  
  377. /*
  378.  * mark edges crossing ``active'' AOI bounds, 
  379.  * set aoiFlags for out-of-bounds edge endpoints
  380.  */
  381. void
  382. mark_eEdges (struct vSite *v, struct vEdge *e, int ne)
  383. {
  384.   int ie;
  385.   int e_vO, e_vF;
  386.  
  387.   for (ie = 0; ie < ne; ie++) {
  388.     e_vO = (e + ie)->vO;
  389.     e_vF = (e + ie)->vF;
  390.     if (check_e (e_vO, e_vF) == UnSet) {
  391.       if (((v + e_vO)->aoiFlag = check_v (v + e_vO)) == Set)
  392.         (e + ie)->vO = -1;
  393.       if (((v + e_vF)->aoiFlag = check_v (v + e_vF)) == Set)
  394.         (e + ie)->vF = -1;
  395.     }
  396.   }
  397. }
  398.  
  399.  
  400.  
  401. /*
  402.  * joint probability distribution, p(n, A)
  403.  * construct joint probability distribution, p(n, A), of poly edge number
  404.  * n, and Voronoi polygon area, A (see p_of_nA(), anal_gt.c)
  405.  */
  406. double
  407. p_of_nVA (int *npn, unsigned int **a_n, int ns, struct vPoly *p)
  408. {
  409.   int is, cne;
  410.   int nma;
  411.   double ma;
  412.  
  413.   nma = 0;
  414.   ma = 0.0;
  415.   for (is = 0; is < ns; is++) {
  416.     if (((p + is)->aoiFlag == UnSet) &&
  417.         ((p + is)->eFlag == UnSet) &&
  418.         ((p + is)->lFlag == UnSet)) {
  419.       cne = (p + is)->ne;
  420.       *(a_n[cne] + npn[cne]) = (unsigned int) (p + is)->area;
  421.       npn[cne]++;
  422.  
  423.       ma += (p + is)->area;
  424.       nma++;
  425.     }
  426.   }
  427.   ma /= (double) nma;
  428.   return (ma);
  429. }
  430.  
  431.  
  432. /*
  433.  * determine number of (unflagged) polygons,
  434.  * with edge numbers between nel and neu;
  435.  *
  436.  * nea array index: i = (ne = (p+is)->ne) - nel;
  437.  */
  438. int *
  439. pe_dist (struct vPoly *p, int ns, int nel, int neu)
  440. {
  441.   int is, ne;
  442.   int *nea;
  443.  
  444.   if ((nea = (int *) calloc (16, sizeof (int))) == NULL)
  445.       fail_alloc ("nea", 1);
  446.  
  447.   for (is = 0; is < ns; is++) {
  448.     if (((p + is)->eFlag == UnSet) &&
  449.         ((p + is)->lFlag == UnSet)) {
  450.       if ((ne = (p + is)->ne) < 16)
  451.         nea[ne]++;
  452.     }
  453.   }
  454.   return (nea);
  455. }
  456.  
  457.  
  458. /*
  459.  * polygon associated site, area, etc
  460.  */
  461. void
  462. poly_geom (struct vSite *s, struct vSite *v, struct vEdge *e, struct vPoly *p, struct Tuple *pem, int ns, int ne, int CPV)
  463. {
  464.   int ie, is;
  465.   int e_vO, e_vF;
  466. #if BOND
  467.   Boolean eFlag;
  468.   double l1, l2;
  469. #endif
  470.   double sarea;
  471.  
  472.  
  473. /* 
  474.  * sort edge structure in order of increasing edge index 
  475.  */
  476. #if defined(LINUX)
  477.   qsort (e, ne, sizeof (struct vEdge), (__compar_fn_t) e_comp);
  478. #else
  479.   qsort (e, ne, sizeof (struct vEdge), e_comp);
  480. #endif
  481. #ifdef SHOW_SORT
  482.   printf ("\n...edges after sorting in order of edge indices:\n");
  483.   for (i = 0; i < ne; i++)
  484.     printf ("  e %3d:  vO: %3d vF: %3d  sO: %3d sF: %3d\n",
  485.       (e + i)->edgenbr, (e + i)->vO, (e + i)->vF, (e + i)->sO, (e + i)->sF);
  486. #endif
  487.  
  488.  
  489. /*
  490.  * evaluate V. polygon area and set of angles subtended by edges
  491.  * if desired, collect (valid) indices of polygon vertices
  492.  */
  493.   for (is = 0; is < ns; is++) { /* loop over polygons: one per site */
  494.     (p + is)->coord.x = (s + is)->coord.x;
  495.     (p + is)->coord.y = (s + is)->coord.y;
  496.     (p + is)->area = (float) 0.0;
  497.     for (ie = 0; ie < (p + is)->ne; ie++) {  /* loop over poly edges */
  498.       e_vO = (e + ((p + is)->pei[ie]))->vO;
  499.       e_vF = (e + ((p + is)->pei[ie]))->vF;
  500.       if (check_e (e_vO, e_vF) == UnSet) {
  501.         sarea = T_area ((v + e_vF), (v + e_vO), (s + is));
  502.         (p + is)->area += (float) (fabs (0.5 * sarea));
  503.  
  504.         if (CPV == 1) {
  505.           if (SIGN (sarea) < 0)
  506.             (p + is)->pvi[ie] = e_vO;
  507.           else
  508.             (p + is)->pvi[ie] = e_vF;
  509.         }
  510. /*                              (pem+ie) = edge_mp(v+e_vF, v+e_vO, ie); */
  511.       }
  512.       else {
  513.         (p + is)->pvi[ie] = -1;
  514.       }
  515.     }
  516.  
  517. /*
  518.  * sort polygon edges to determine nn `bond' angles
  519.  */
  520.  
  521. #if BOND
  522.     if (eFlag == UnSet) {
  523.       sort_poly_edges (pem, s + is, p + is);
  524.  
  525.       for (ie = 0; ie < (p + is)->ne; ie++) {
  526.         sarea = T_area ((), (), (s + is));
  527.  
  528.         l1 = slen (pem + ie, s + is);
  529.         l2 = slen (pem + ie + 1, s + is);
  530.         (p + is)->sphi[ie] = (float) sarea / (l1 * l2);
  531.       }
  532.     }
  533. #endif
  534.   }
  535. }
  536.  
  537. /*
  538.  * check whether site lies outside AOI; if so, return Set;
  539.  * (same as function check_v())
  540.  */
  541. Boolean
  542. check_s (s)
  543.      struct vSite *s;
  544. {
  545.   int sx, sy;
  546.  
  547.   sx = (int) s->coord.x;
  548.   sy = (int) s->coord.y;
  549.   if (sx < AULX)
  550.     return (Set);
  551.   if (sy < AULY)
  552.     return (Set);
  553.   if (sx > ALRX)
  554.     return (Set);
  555.   if (sy > ALRY)
  556.     return (Set);
  557.  
  558.   return (UnSet);
  559. }
  560.  
  561. /*
  562.  * set aoiFlag for all Sites which fall outside of ``active'' AOI
  563.  */
  564. void
  565. mark_eSites (s, ns)
  566.      struct vSite *s;
  567.      int ns;
  568. {
  569.   int is;
  570.  
  571.   for (is = 0; is < ns; is++)
  572.     (s + is)->aoiFlag = check_s ((s + is));
  573. }
  574.  
  575.  
  576. /*
  577.  * determine number of sites, within ``active'' AOI, 
  578.  * with coordination numbers between ncl and ncu;
  579.  *
  580.  * nnna array index: i = (nc = (s+is)->nnn) - ncl;
  581.  */
  582. int *
  583. count_defects (s, ns, ncl, ncu)
  584.      struct vSite *s;
  585.      int ns, ncl, ncu;
  586. {
  587.   int is;
  588.   int nc;
  589.   int *nnna;
  590.  
  591.   if ((nnna = (int *) calloc (16, sizeof (int))) == NULL)
  592.       fail_alloc ("nnna", 1);
  593.  
  594.   for (is = 0; is < ns; is++) {
  595.     if (((s + is)->eFlag == UnSet) &&
  596.         ((s + is)->aoiFlag == UnSet)) {
  597.       if ((nc = (s + is)->nnn) < 16)
  598.         nnna[nc]++;
  599.     }
  600.   }
  601.   return (nnna);
  602. }
  603.  
  604.  
  605. /*
  606.  * check whether vertex lies outside AOI; if so, return Set;
  607.  * (same as function check_s())
  608.  */
  609. Boolean
  610. check_v (v)
  611.      struct vSite *v;
  612. {
  613.   int vx, vy;
  614.  
  615.   vx = (int) v->coord.x;
  616.   vy = (int) v->coord.y;
  617.  
  618.   if (ACTIVE_AOI == 1) {        /* enforce new AOI bounds */
  619.     if (vx < AULX)
  620.       return (Set);
  621.     if (vy < AULY)
  622.       return (Set);
  623.     if (vx > ALRX)
  624.       return (Set);
  625.     if (vy > ALRY)
  626.       return (Set);
  627.   }
  628.   else {                        /* enforce orig display AOI bounds */
  629.     if (vx < ULX)
  630.       return (Set);
  631.     if (vy < ULY)
  632.       return (Set);
  633.     if (vx > LRX)
  634.       return (Set);
  635.     if (vy > LRY)
  636.       return (Set);
  637.   }
  638.   return (UnSet);
  639. }
  640.  
  641.  
  642. /*
  643.  * determine site coordination:
  644.  * this is given by the number of edges of non-zero length associated
  645.  * with a given site in such a way that their bisectors share one common
  646.  * vertex, namely the site in question; 
  647.  *
  648.  * mark ``edge'' sites, by setting eFlag:
  649.  * these are sites whose associated V. polygon contains vertices 
  650.  * which lie outside the display AOI: this includes those vertices 
  651.  * connected by edges marked -1 in struct e; 
  652.  *
  653.  * the following routine assumes the vEdge array to be suitably sorted;
  654.  */
  655. void
  656. site_coordination (s, v, e, ns, ne)
  657.      struct vSite *s, *v;
  658.      struct vEdge *e;
  659.      int ns, ne;
  660. {
  661.   int ie, is;
  662.   int e_vO, e_vF;
  663.   int efl;
  664.  
  665.  
  666. /* 
  667.  * first, search sO member 
  668.  */
  669. #if defined(LINUX)
  670.   qsort (e, ne, sizeof (struct vEdge), (__compar_fn_t) esO_comp);
  671. #else
  672.   qsort (e, ne, sizeof (struct vEdge), esO_comp);
  673. #endif
  674. #ifdef SHOW_SORT
  675.   printf ("\n...edges after sorting in order of sO indices:\n");
  676.   for (i = 0; i < ne; i++)
  677.     printf ("  e %3d:  vO: %3d vF: %3d  sO: %3d sF: %3d\n",
  678.       (e + i)->edgenbr, (e + i)->vO, (e + i)->vF, (e + i)->sO, (e + i)->sF);
  679. #endif
  680.   printf ("\n");
  681.   ie = 0;
  682.   for (is = 0; is < ns; is++) {
  683.     efl = 0;
  684.     while ((e + ie)->sO == (s + is)->sitenbr) {
  685.       (s + is)->nnn++;
  686.  
  687.       e_vO = (e + ie)->vO;
  688.       e_vF = (e + ie)->vF;
  689.       if (check_e (e_vO, e_vF) == Set)
  690.         efl++;
  691.  
  692.       ie++;
  693.     }
  694.     if (efl > 0)
  695.       (s + is)->eFlag = Set;
  696.   }
  697.   printf ("\n");
  698.  
  699. /* 
  700.  * now, search sF member 
  701.  */
  702. #if defined(LINUX)
  703.   qsort (e, ne, sizeof (struct vEdge), (__compar_fn_t) esF_comp);
  704. #else
  705.   qsort (e, ne, sizeof (struct vEdge), esF_comp);
  706. #endif
  707. #ifdef SHOW_SORT
  708.   printf ("\n...edges after sorting in order of sF indices:\n");
  709.   for (i = 0; i < ne; i++)
  710.     printf ("  e %3d:  vO: %3d vF: %3d  sO: %3d sF: %3d\n",
  711.       (e + i)->edgenbr, (e + i)->vO, (e + i)->vF, (e + i)->sO, (e + i)->sF);
  712. #endif
  713.  
  714.   ie = 0;
  715.   for (is = 0; is < ns; is++) {
  716.     efl = 0;
  717.     while ((e + ie)->sF == (s + is)->sitenbr) {
  718.       (s + is)->nnn++;
  719.  
  720.       e_vO = (e + ie)->vO;
  721.       e_vF = (e + ie)->vF;
  722.       if (check_e (e_vO, e_vF) == Set)
  723.         efl++;
  724.  
  725.       ie++;
  726.     }
  727.     if (efl > 0)
  728.       (s + is)->eFlag = Set;
  729.   }
  730. }
  731.